#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
bool geats;
const int maxn=3e5+2;
const int mod=1e9+7;
const ull pri=37;
int T;
int n,len;
char p[maxn];
ull pw[maxn],ha[maxn];
void upd(int &x,int v){((x+=v)>=mod)?(x-=mod):x;}
namespace io{
    int read(){
        int x=0,f=0;
        char ch=getchar();
        while(!isdigit(ch))f=((ch=='-')?-f:f),ch=getchar();
        while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return x;
    }
    int ot[40],tp;
    void write(int x){
        if(x==0){putchar('0');return ;}
        while(x)ot[++tp]=x%10,x/=10;
        while(tp)putchar(ot[tp--]+'0');
        return ;
    }
}
namespace fib{
    struct node_matrix{
        int ar[2][2];
        void init(int ty){
            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++)ar[i][j]=0;
                if(ty)ar[i][i]=1;
            }
            return ;
        }
        node_matrix operator * (const node_matrix &A)const{
            node_matrix ret;
            ret.init(0);
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                    for(int k=0;k<2;k++)
                        upd(ret.ar[i][j],1ll*ar[i][k]*A.ar[k][j]%mod);
            return ret;
        }
    }src,mul;
    node_matrix f_pow(node_matrix x,int p){
        node_matrix ret;
        ret.init(1);
        while(p){
            if(p&1)ret=ret*x;
            x=x*x;
            p>>=1;
        }
        return ret;
    }
    node_matrix fib(int x){
        src.ar[0][0]=0,src.ar[0][1]=1;
        src.ar[1][0]=0,src.ar[1][1]=0;
        mul.ar[0][0]=0,mul.ar[0][1]=1;
        mul.ar[1][0]=1,mul.ar[1][1]=1;
        return src*f_pow(mul,x-1);
    }
}
namespace BA{
    struct node_matrix{
        int ar[3][3];
        void init(int ty){
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++)ar[i][j]=0;
                if(ty)ar[i][i]=1;
            }
            return ;
        }
        node_matrix operator * (const node_matrix &A)const{
            node_matrix ret;
            ret.init(0);
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    for(int k=0;k<3;k++)
                        upd(ret.ar[i][j],1ll*ar[i][k]*A.ar[k][j]%mod);
            return ret;
        }
    }src,mul;
    node_matrix f_pow(node_matrix x,int p){
        node_matrix ret;
        ret.init(1);
        while(p){
            if(p&1)ret=ret*x;
            x=x*x;
            p>>=1;
        }
        return ret;
    }
    node_matrix BA(int x){
        src.ar[0][0]=0,src.ar[0][1]=0,src.ar[0][2]=1;
        src.ar[1][0]=0,src.ar[1][1]=0,src.ar[1][2]=0;
        src.ar[2][0]=0,src.ar[2][1]=0,src.ar[2][2]=0;
        mul.ar[0][0]=1,mul.ar[0][1]=1,mul.ar[0][2]=0;
        mul.ar[1][0]=1,mul.ar[1][1]=2,mul.ar[1][2]=0;
        mul.ar[2][0]=1,mul.ar[2][1]=1,mul.ar[2][2]=1;
        return src*f_pow(mul,x);
    }
}
string get(int id){
    if(id==0)return "0";
    if(id==1)return "1";
    return get(id-1)+get(id-2);
}
ull query(int l,int r){
    return ha[r]-ha[l-1]*pw[r-l+1];
}
void getha(string s){
    for(int i=1,siz=s.size();i<=siz;i++)ha[i]=ha[i-1]*pri+(ull)(s[i-1]-'0');
    return ;
}
bool check(string s,ull now){
    // if(s=="101")geats=1;
    // else geats=0;
    getha(s);
    for(int i=1,siz=s.size();i+len-1<=siz;i++){
        if(now==query(i,i+len-1))return 1;
    }
    return 0;
}
int f_pow(int x,int p){
    int ret=1;
    while(p){
        if(p&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;
        p>>=1;
    }
    return ret;
}
int calc(string A,string B,ull now){
    int sizA=A.size(),sizB=B.size(),ret=0;
    getha(A+B);
    for(int i=0;i<sizA;i++){
        if(i+len-1>=sizA&&i+len-1<sizA+sizB)ret+=(query(i+1,i+len)==now);
    }
    return ret;
}
int bav(int x){
    return BA::BA(x/2).ar[0][x&1];
}
int solve(){
    if(len==1)return (p[1]=='1')?((n==0)?0:fib::fib(n).ar[0][1]):((fib::fib(n+1).ar[0][1]-((n==0)?0:fib::fib(n).ar[0][1])+mod)%mod);
    ull now=0;
    for(int i=1;i<=len;i++)now=now*pri+(ull)(p[i]-'0');
    fib::node_matrix ma;
    int whi=1;
    while(true){
        ma=fib::fib(whi);
        if(ma.ar[0][1]>=len)break;
        whi++;
    }
    whi--;
    // printf("pas whi: %d\n",whi);
    // cout<<get(whi)<<'\n';
    int count_fail=0;
    while(!check(get(whi),now)&&count_fail<3)whi++,count_fail++;
    // printf("whi: %d\n",whi);
    // cout<<get(whi)<<'\n';
    // cout<<get(n)<<'\n';
    // cout<<get(n-whi+1)<<'\n';
    if(count_fail==3)return 0;
    string A=get(whi),B=get(whi-1);
    getha(A);
    int numA=0,numAA=0,numAB=0,numBA=0;
    for(int i=1,siz=A.size();i+len-1<=siz;i++)numA+=(now==query(i,i+len-1));
    if(n<whi)return 0;
    if(n==whi)return numA;
    numAA=calc(A,A,now),numAB=calc(A,B,now),numBA=calc(B,A,now);
    // printf("num: %d %d %d %d\n",numA,numAA,numAB,numBA);
    ma=fib::fib(n-whi+1);
    // printf("num: %d %d %d %d\n",ma.ar[0][1],bav(n-1-whi),ma.ar[0][0],bav(n-whi));
    int ans=0;
    upd(ans,1ll*ma.ar[0][1]*numA%mod);
    upd(ans,1ll*ma.ar[0][0]*numAB%mod);
    upd(ans,1ll*bav(n-whi)*numBA%mod);
    upd(ans,1ll*bav(n-1-whi)*numAA%mod);
    return ans;
}
void pre_calc(){
    pw[0]=1;for(int i=1;i<maxn;i++)pw[i]=pw[i-1]*pri;
    return ;
}
int main(){
    freopen("brotherhood.in","r",stdin);
    freopen("brotherhood.out","w",stdout);
    n=io::read(),T=io::read();
    n--;
    pre_calc();
    while(T--){
        scanf("%s",p+1);
        len=strlen(p+1);
        io::write(solve());
        putchar('\n');
    }
    return 0;
}